﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace ParallelRuntimeLibrary.Collections
{
    /// <summary>
    /// Represend list have two end, public for all threads (Pop), private for one thread (Push, and pop).
    /// Public Private List implemnted using Work-Stealing Queue
    /// </summary>
    /// <typeparam name="T">Specifies the type of elements in the list</typeparam>
    public class PublicPrivateList<T>
    {
        private const int InitialSize = 32;

        private T[] Array;

        private int Mask;
        private volatile int HeadIndex;
        private volatile int TailIndex;

        private object ForeignLock;
        private int mOwnerThread;

        /*///////////////////////////////////////////////////////////////////////////////////////////////*/

        public PublicPrivateList()
        {
            Array = new T[InitialSize];
            ForeignLock = new object();
            HeadIndex = TailIndex = 0;
            Mask = InitialSize - 1;
        }

        public void OwnIt()
        {
            lock (ForeignLock)
            {
                Interlocked.Exchange(ref mOwnerThread, Thread.CurrentThread.ManagedThreadId);
            }
        }

        /*///////////////////////////////////////////////////////////////////////////////////////////////*/

        #region Public - Private List

        public void PrivatePush(T value)
        {
            int tail = TailIndex;
            if (tail < HeadIndex + Mask)
            {
                Array[tail & Mask] = value;
                TailIndex = tail + 1;
            }
            else
            {
                lock (ForeignLock)
                {
                    int head = HeadIndex;

                    int count = TailIndex - HeadIndex;

                    if (count >= Mask)
                    {

                        T[] newArray = new T[Array.Length << 1];

                        System.Array.Copy(Array, newArray, Array.Length);

                        Array = newArray;
                        HeadIndex = 0;
                        TailIndex = tail = count;
                        Mask = (Mask << 1) | 1;
                    }

                    Array[tail & Mask] = value;
                    TailIndex = tail + 1;
                }
            }
        }

        public bool PrivatePop(out T value)
        {
            int tail = TailIndex;
            if (HeadIndex >= tail)
            {
                value = default(T);
                return false;
            }

#pragma warning disable 0420

            tail -= 1;
            Interlocked.Exchange(ref TailIndex, tail);
            if (HeadIndex <= tail)
            {
                value = Array[tail & Mask];
                return true;
            }
            else
            {
                lock (ForeignLock)
                {
                    if (HeadIndex <= tail)
                    {
                        // Element still available. Take it.
                        value = Array[tail & Mask];
                        return true;
                    }
                    else
                    {
                        // We lost the race, element was stolen, restore the tail.
                        TailIndex = tail + 1;
                        value = default(T);
                        return false;
                    }
                }
            }

        }

        /*/////////////////////////////////////////////////////////////////////////////*/

        public bool PublicPop(out T value)
        {
            return PublicPop(out value, 0);
        }

        public bool PublicPop(out T value, int millisecondsTimeout)
        {
            bool taken = false;
            try
            {
                taken = Monitor.TryEnter(ForeignLock, millisecondsTimeout);
                if (taken)
                {
                    int head = HeadIndex;
                    Interlocked.Exchange(ref HeadIndex, head + 1);
                    if (head < TailIndex)
                    {
                        value = Array[head & Mask];
                        return true;
                    }
                    else
                    {
                        HeadIndex = head;
                        value = default(T);
                        return false;
                    }
                }
                else
                {
                    value = default(T);
                    return false;
                }
            }
            finally
            {
                if (taken)
                    Monitor.Exit(ForeignLock);
            }
        }

        #endregion
    }
}
